package ui.clustering;

import java.util.ArrayList;
import java.util.Random;

/**
 * a fast approximate way that mapping objects with a distance(or similarity)
 * function to k-dimension points
 * 
 * @author huangcd
 * 
 */
public class FastMap
{
    // a double[] stands for the coordinate for all elements in a single
    // dimension
    private ArrayList<double[]> revCoordinateList = new ArrayList<double[]>();
    private double[][]          disMatrix         = null;
    private int                 size              = -1;

    public ArrayList<double[]> map(double[][] distanceMatrix, int dimension)
            throws Exception
    {
        // for (double[] arr : distanceMatrix)
        // {
        // System.err.println(Arrays.toString(arr));
        // }
        this.disMatrix = distanceMatrix;
        size = disMatrix.length;
        for (int i = 0; i < size; i++)
            if (disMatrix[i].length != size)
                throw new Exception("distance matrix size not match");
        revCoordinateList.clear();
        internalMap(dimension);
        ArrayList<double[]> result = new ArrayList<double[]>();
        for (int i = 0; i < size; i++)
        {
            double[] coordinate = new double[dimension];
            for (int j = 0; j < dimension; j++)
            {
                coordinate[j] = revCoordinateList.get(j)[i];
            }
            result.add(coordinate);
        }
        // for (double[] arr : result)
        // {
        // System.err.println(Arrays.toString(arr));
        // }
        return result;
    }

    private void internalMap(int k)
    {
        ArrayList<Integer> pivots = pickPivotsIndex();
        int a = pivots.get(0), b = pivots.get(1);
        double Dab = Math.pow(disMatrix[a][b], 2);
        double[] revCoordinate = new double[size];
        double min = Double.MAX_VALUE;
        double max = Double.MIN_VALUE;
        for (int i = 0; i < size; i++)
        {
            revCoordinate[i] = (Math.pow(disMatrix[a][i], 2) + Dab - Math.pow(
                    disMatrix[b][i], 2))
                    / 2 * disMatrix[a][b];
            min = Math.min(min, revCoordinate[i]);
            max = Math.max(max, revCoordinate[i]);
        }
        double[][] newDisMatrix = new double[size][size];
        // update matrix
        for (int i = 0; i < size; i++)
        {
            for (int j = 0; j < size; j++)
            {
                if (Math.pow(disMatrix[i][j], 2) >= Math.pow(revCoordinate[i]
                        - revCoordinate[j], 2))
                    newDisMatrix[i][j] = Math.sqrt(Math.pow(disMatrix[i][j], 2)
                            - Math.pow(revCoordinate[i] - revCoordinate[j], 2));
                else
                {
                    newDisMatrix[i][j] = 0;
                }
            }
        }
        disMatrix = newDisMatrix;
        for (int i = 0; i < size; i++)
        {
            revCoordinate[i] = (revCoordinate[i] - min) / (max - min);
        }
        revCoordinateList.add(revCoordinate);
        k--;
        if (k > 0)
            internalMap(k);
    }

    private ArrayList<Integer> pickPivotsIndex()
    {
        ArrayList<Integer> result = new ArrayList<Integer>();
        Random rand = new Random(System.currentTimeMillis());
        int index = rand.nextInt(size);
        result.add(0, index);
        for (int i = 0; i < 3; i++)
        {
            int maxElemIndex = -1;
            double maxDistance = Double.MIN_VALUE;
            index = result.get(0);
            for (int j = 0; j < size; j++)
            {
                if (disMatrix[index][j] > maxDistance)
                {
                    maxDistance = disMatrix[index][j];
                    maxElemIndex = j;
                }
            }
            if (maxElemIndex == -1 || maxElemIndex == result.get(0))
            {
                while (maxElemIndex != result.get(0))
                    maxElemIndex = rand.nextInt(size);
            }
            result.add(0, maxElemIndex);
        }
        return result;
    }
}
